package top.minuy.structure.map;
/**
 * 链表映射
 *
 * @author Minuy
 * @time 17:05
 * @date 2021/9/11
 * @param <K> 键，泛型支持，不需要可比较，使用equals方法对比
 * @param <V> 值，泛型支持
 */
public class LinkedListMap<K,V> implements Map<K,V> {
    /**
     * 链表节点
     */
    class Node{
        public K key;
        public V val;
        Node next;

        public Node(K key,V val,Node next){
            this.key = key;
            this.val = val;
            this.next = next;
        }

        public Node(K key){
            this(key,null,null);
        }

        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString() {
            return key.toString()+" : "+val.toString();
        }
    }

    Node dummyHead;
    int size;

    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    /**
     * 通过k值获取一个节点
     * @param key 键
     * @return 节点，如果不存在则返回空
     */
    private Node getNode(K key){
        Node cur = dummyHead.next;  // 可以直接跳过第一个的
        while (cur!=null){
            if(cur.key.equals(key)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 向字典中添加键值对
     *
     * @param key 键
     * @param val 值
     */
    @Override
    public void add(K key, V val) {
        /*Node cur=dummyHead;
        while (true){
            // 如果存在，修改一下值
            if(cur.k.equals(k)){
                cur.v = v;
                return;
            }

            // 如果不为空，遍历所有看是否有相等的k，再添加
            if(cur.next!=null){
                cur = cur.next;
            }else {
                cur.next = new Node(k,v);
                return;
            }
        }

         */
        Node tag = getNode(key);
        if(tag!=null){
            tag.val = val;
        }else {
            dummyHead.next = new Node(key,val,dummyHead.next);
            size++;
        }
    }

    public K[] getKeyArray(){
        K[] array = (K[]) new Object[getSize()];
        Node cur = dummyHead;
        for (int i=0;i<getSize();i++){
            // 一定不要忘记位移
            // 2021.11.9 修复此Bug：约 1.5h
            cur = cur.next;
            array[i] = cur.key;
        }
        return array;
    }

    /**
     * 删除一个键值对
     *
     * @param key 要被删除的键
     * @return 返回被删除键的值，如若键不存在，返回空
     */
    @Override
    public V remove(K key) {
        /*
        Node cur = dummyHead.next;
        while (cur!=null){
            if(cur.next == null){  // 如果找到尾了
                return null;  // 返回空，表示没删除什么
            }else if(key.equals(cur.next.key)){
                Node delNode = cur.next;  // 要被删除的节点
                V v = delNode.val;  // 暂存要被删除节点的值
                cur.next = delNode.next;  // 当前节点直接指向要删除节点的下一个节点
                delNode.next = null;  // 删除要删除的节点
                size--;  // 维护大小变量
                return v;
            }else {
                cur = cur.next;
            }
        }*/

        // 1.找到前驱
        Node prev = dummyHead;
        while (prev.next!=null){
            if(prev.next.key.equals(key)){
                break;
            }
            prev = prev.next;
        }

        if(prev.next!=null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            return delNode.val;
        }

        return null;
    }

    /**
     * 查询键是否存在
     *
     * @param key 要查询的键
     * @return 此键是否存在
     */
    @Override
    public boolean contains(K key) {
        Node node = getNode(key);
        return node!=null;
    }

    /**
     * 获取一个键的值
     *
     * @param key 键
     * @return 值
     */
    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node == null?null:node.val;
    }

    /**
     * 修改一个键值对
     *
     * @param key 键
     * @param newVal 值
     */
    @Override
    public void set(K key, V newVal) {
        Node node = getNode(key);
        if(node==null){ // node 为空，直接退出
            throw new IllegalArgumentException("Set failed. The \""+key+"\" is not exists.");
        }

        node.val = newVal;
    }

    /**
     * 获取字典的大小
     *
     * @return 字典的大小
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断字典是否为空
     *
     * @return 字典是否为空
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}
